This invention pertains to wavelength division multiplexing (WDM) optical networks, particularly to WDM networks whose design avoids blocking of communication paths among nodes.
Demand for network bandwidth has grown at very fast pace in recent years. This is mostly due to the very large increase in Internet traffic. It has been estimated that Internet traffic has been growing exponentially at an annual rate around 300%. The overall volume of data traffic overtook that of voice traffic for the first time around the year 2000. This increase has resulted in the deployment of optical networks to meet the ever-expanding demand. Due to recent advances such as Wavelength Division Multiplexing (WDM) and Dense Wavelength Division Multiplexing (DWDM), optical networks have been able, so far, to provide the bandwidth needed to meet demand. Optical long-haul networks (which were originally deployed in the 1980s for carrying long distance voice traffic), have evolved over the years. Optical networks have become ubiquitous not only at the long-haul level but also at the Metropolitan Area Network level.
The ability to supply continually increasing bandwidth will be enhanced if optical-electronic-optical conversions can be avoided at intermediate nodes. Recent years have witnessed much activity in optical components such as optical cross connects, optical wavelength routing switches, optical add/drop multiplexers, optical amplifiers, etc. Ideally, one would prefer an all-optical network, one in which all connections between source and destination nodes are optical, with no need for optical-electronic-optical conversions.
A wavelength division multiplexing (WDM) network is one in which multiple wavelengths of light are used simultaneously to transmit information on a single path or fiber. A major issue in WDM all-optical networks is that of establishing efficient lightpaths. In existing WDM networks, a call that arrives at a particular node, say Nx, on a given wavelength, say λi, can either be forwarded to the next node, say Ny on λi (if λi is free on the Nx→Ny link), or it must be converted to another available wavelength before being re-transmitted, if possible. If neither is possible, then the call is said to be “blocked.” Such blockage can be due to several factors: the unavailability of a λi on the Nx→Ny link, the unavailability of a wavelength converter at Nx, or the unavailability of any free wavelength from Nx to Ny. The blocked call in such a case is generally dropped, and the source generally then re-attempts the connection at a latter time. In time-critical applications, the resulting delay may not be acceptable.
If converters are not available in the network, a lightpath must use the same wavelength on each link in the route. Such a restriction is called the wavelength-continuity constraint. Under such a constraint, establishing a lightpath has two aspects: (1) determining the route from source to destination; and (2) assigning a particular wavelength to the lightpath. This is known as the routing and wavelength assignment (RWA) problem. Wavelength converters are expensive and introduce noise to a signal. For that reason it is highly desirable to minimize the number of converters used in a network, or to minimize the blocking probability given a certain number of converters.
To the knowledge of the inventors, before the priority date for the present application, no one had previously reported a non-trivial solution to the problem of designing non-blocking, lightpath-routed WDM (or DWDM) all-optical networks. In recent years much attention has been given to the development of new topologies and new routing schemes for optical networks, especially at the metropolitan area network level. There are two reasons for the recent intense interest in this area. First, networks with higher connectivity than the traditional “ring” topology can offer higher bandwidths and better scalabilities. Second, networks with higher connectivity can offer better fault resilience and more efficient provisioning. There are different approaches to the routing and wavelength assignment problem. One previous method assumes no wavelength converters are used, and assigns wavelengths on-line (in real-time) based on the availability of wavelengths at the source node. In this scheme, the lightpath is necessarily established under the wavelength continuity constraint—since no converters are available. However, if the wavelength selected at the source is not available along every link in the path, then the call is blocked and a connection will have to be re-attempted at a later time.
Wavelength converters can be used in establishing lightpaths to reduce the probability of blocking. In general, wavelength converters are expensive and are prone to introducing noise to a signal. Thus wavelength converters represent a less-than ideal solution. Wavelength converters are typically one of two types: full-range or partial-range wavelength converters. A full-range wavelength converter can convert a signal on wavelength λi to any of the output wavelengths. A partial-range wavelength converter can only convert to a proper subset of the output wavelengths.
Routing may be fixed or adaptive. In fixed routing schemes the route is determined based solely on the identity of the source and destination nodes. In some fixed routing schemes, more than one path may be predetermined and stored in an ordered list at the source node's routing table. Adaptive schemes are more complex to implement. They take network conditions into account while making routing decisions.
U.S. Pat. No. 6,456,588 discloses a telecommunications network architecture having a plurality of n-dimensional hypercubes (3≦n), a plurality of nodes, and a plurality of links. Each hypercube is interconnected with at least-one other hypercube, and has 2n vertex nodes. Each vertex node has a degree n, meaning that it is connected by links to n other vertex nodes. Features of the network were said to include decentralized node control, substantially independent traffic management within each hypercube, working and protection links with less traffic-bearing capacity, vertex node labeling that reduced inter-nodal communication, and less complex traffic routing and recovery algorithms. This disclosure addresses the problem of bypassing or recovering from faults on a network, but does not address the problem of blocking.
C. Zhou et al., “Wide-Sense Nonblocking Multicast in a Class of Regular Optical WDM Networks,” IEEE Trans. Comm., vol. 50, pp. 126-134 (2002) describes a study of multicast communications in a class of optical WDM networks with regular topologies such as linear arrays, rings, meshes, tori, and hypercubes. The authors derived what were said to be necessary and sufficient conditions on the minimum number of wavelengths required for a WDM network to be wide-sense nonblocking for multicast communication under some commonly used routing algorithms. The authors addressed a case in which the destinations of a multicast operation receive different (individualized) messages. The method required N/2 wavelengths to achieve non-blocking (where N is the number of nodes). The method did not address the issue of identical copies delivered to destinations of a multicast operation, or the case of all-to-all broadcasting. Also, the method addressed only the case of a single source, but not the case of multiple concurrent sources.
P. Saengudomlert, “Architectural Study of High-Speed Networks with Optical Bypassing,” PhD Thesis, Massachusetts Institute of Technology (September 2002), at pages 17-23 and 63-67 addresses the RWA problem for all-to-all broadcast in an n-dimensional hypercube. The proposed non-blocking solution employs N/2 wavelengths per path or fiber, where N is the total number of nodes.
B. Beauquier et al., “Graph Problems Arising in Wavelength-Routing in All-Optical Networks,” Proc. 2nd Workshop Optics & Comp. Sci., IPPS (1997) discloses theoretical results obtained for wavelength routing in WDM all-optical networks. The authors concluded that in a hypercube any a priori-known permutation may be routed in a blocking-free manner using two wavelengths.
A trivial, but generally impractical, solution to the blocking-free routing problem is a network in which each node has a direct (or dedicated) connection to every other node. In such a fully-connected system a single wavelength would suffice, since no intermediate nodes would need to be involved in any communications. However, with N nodes the number of connections per node is (N−1). In a ring topology with N nodes, [N/2] wavelengths are needed to achieve non-blocking, all-to-all connectivity. The cases of 2-D mesh and 2-D torus are difficult to solve optimally; to the knowledge of the inventors, before the priority date claimed by the present application, it had not been reported for these topologies how many wavelengths would be needed, nor how to accomplish non-trivial, blocking-free routing.